package DataStructure.uf;

public class UF_Tree {
    private int[] eleAndGroup;//记录节点元素和所在组的标识
    private int count;//组的个数

    public UF_Tree(int N){
        this.count=N;
        this.eleAndGroup=new int[N];

        for (int i = 0; i < eleAndGroup.length; i++) {
            eleAndGroup[i]=i;
        }
    }

    public int count(){
        return count;
    }

    public boolean connected(int p,int q){
        return find(p)==find(q);
    }

    //元素p所在的标识符
    public int find(int p){
        while (true){
            if(p==eleAndGroup[p]){
                return p;
            }
            p=eleAndGroup[p];
        }
    }

    //合并
    public void union(int p,int q){
        //找到p和q所在组对应的数的根节点
        int pRoot = find(p);
        int qRoot = find(q);
        //如果p和q已经在同一分组就不需要合并
        if(pRoot==qRoot){
            return;
        }
        //让p所在数的根节点的父节点为q所在树的根节点即可
        eleAndGroup[pRoot]=qRoot;
        this.count--;
    }
}
